Conventionally, various data structures are constructed by storing pointers with a certain technique in Random Access Memory (hereinafter referred to as “RAM”) having one or more addresses, which is a typical main memory of a computer, to promote efficiency of information expression and increase the speed of operation.
For instance, there are techniques for expressing structures among a plurality of data as a linear list, binary tree, tree, or various graphs by storing a certain pointer for another node in a portion of RAM corresponding to the first node. Those data structures provide certain fixed operations and functions.
However, there has been no known effective maintenance/management techniques for providing equivalency among the functions of a plurality of data structures arranged upon one or a plurality of RAM.
A conventional technique for maintaining equivalency among a plurality data structures is described below.
First, there is a technique for securing functional equivalency among a plurality of data structures by performing with exactly the same content and sequence all of the update operations that modify a data structure function and the search operation required for this update operation, not just for a single data structure but also for each of the plurality of data structures.
However, with the first technique, the hassle or the calculation time, required to maintain and manage other data structures that should be reflected an update (modification) (hereinafter referred to as “the copy side data structure”) is the same as the hassle required to maintain and manage the data structure on the modification source side (hereinafter referred to as “the master side data structure”).
More specifically, in order to modify the data structure, in many cases a complex search operation is performed before this modification, and depending on the result of the search the details of the modification vary. Accordingly, with the first technique, unless the same modification procedure including the required search performed for the master side data structure is also performed for the copy side data structure, equivalency between both structures may not be provided. However, with the first technique, the modification processing for the master side data structure and the modification reflecting processing for the copy side data structure require the same amount of calculation time (resources). As a result, there is not much difference between the two sides as far as marginal space allowing other processing such as a search only request to be performed. Accordingly, considerable calculation time is required to implement equivalency among the data structures, and effective division of the processing may not be implemented in a dispersion environment where, for instance, many search requests that are different from the master side are performed on the copy side while the master side concentrates on the processing of the modification requests. In short, it has been impossible with this first technique to effectively reflect only those modifications made to a data structure onto the other data structures and reduce the cost of managing other data structures.
Secondly, there is a technique that, in order to maintain the data structure including the pointer values exactly the same as the content of RAM, all the pointers modified in the course of a modification operation are transmitted one by one and reflected onto the modification target side. With this second technique, the respective data structures (more precisely, each node configuring the respective data structures) are stored in RAM in a portion that is considered to be the same address, and an update (that is, pointer modification information) to one of data structures is copied into RAM which represents other data structures as modifications in the memory content of each address. As long as means for performing appropriate address conversions is employed, a plurality of equivalent data structures may be configured by storing the pointers of identical expressions in the same address in a single storage unit (or computer) or among a plurality of storage units (or computers). Modifications in a data structure may be reflected onto other data structures by structuring a plurality of data structures in this manner and simply copying the pointers as with the other data (codes).
However, the second technique may not be applied to some data structures that are functionally equivalent but allow the pointer structure to take on different forms. For instance, there is a data structure, which is called self-adjusting data structure, that appropriately adjusts pointer structure so that a frequently accessed node becomes a root node. This self-adjusting data structure changes the data structure format to another functionally equivalent format even with a search operation that does not accompany a functional modification. With this self-adjusting data structure, in order to make the stored pointer values match and maintain equivalency, all modifications to the pointer values (the content of each address) that occur as a result of all operations including search operation must be copied. This copying requires transmission of an enormous amount of pointer modification information to the other data structures (or other means for managing data structure), thus the communication traffic in addition to the hassle of managing becomes considerable.
Otherwise, in the case of a data structure such as a high-balanced tree, a large number of pointers may be modified with one modification operation, and as a result, the amount of modified data that must be transmitted increases. Also, in the second technique, there is a restriction whereby the configuration (form) of the data structures on the master side and the copy side must match completely. More specifically, in the case of a binary tree data structure, not only must they be equivalent as far as the binary search tree but also all parent/child relationships among the same corresponding nodes should coincide. (However, if the above address conversion is carried out appropriately, the address of each node and the pointer value do not have to be the same.) In other words, with this second technique, a data structure that is equivalent as a binary search tree between the master side and the copy side, but is different in terms of a specific binary tree structure cannot be used.
For that reason, for instance, when the tree configurations on the master side and the copy side are managed with completely different techniques, in other words, for instance, in the case where the master side utilizes the high-balanced-tree described above so as to manage the tree configuration whereas the copy side utilizes a splay tree so as to perform the search operation, even when the tree configuration is to be modified, the data structure configuration (that is, the form of the tree) before the modification is made and the data structure configuration on the copy side before having to reflect the modified data are completely different. Accordingly, when simply the master side data structure is modified, the modified pointer may not be reflected in the copy side data structure.
In particular, if an attempt is made to implement equivalency among a plurality of data structures arranged respectively upon the main memory of physically different computers using the first or second technique described above, considerable burden would be imposed on the data transmission channel (network) connecting these computers and significant influence imparted to the system as a whole including the data transmission channel.
Moreover, even with the various balanced trees, which are data structures where the form of the data structure is modified only in the case of an update operation, a large number of pointers are modified along with the form modification. As a result, in order to transmit all the modified information of those pointers, although not to the extent as the above-described self-adjusting data structure, considerable load ends up being applied to the data transmission channel that connects each RAM stored with the data structures.
The present invention is brought forth to solve problems of conventional data structure management techniques such as, as described above, the fact that the maintenance/management for the purpose of accomplishing equivalency among the functions of a plurality of data structures arranged upon one or a plurality of RAM requires a great deal of calculation time, there is a large volume of communication, and thus is inefficient.
In addition, an objective thereof is to provide a data structure management apparatus, a data structure management system, a data structure management method, and storage media for storing a data structure management program, which are capable of efficiently maintaining and managing equivalency among a plurality of data structures efficiently by reflecting a modification made to a data structure arranged on one or a plurality of RAM (storage regions) onto the other data structures with the least amount of traffic and calculation time.
Yet another objective of the invention is to maintain and manage the equivalence easily among a part of or the whole data structure arranged on the address unique to each other.